import java.util.ArrayList;
import java.util.Stack;

public class PathSumTwo {
	/*
	 * Given a binary tree and a sum, find all root-to-leaf paths where each
	 * path's sum equals the given sum.
	 * 
	 * For example: Given the below binary tree and sum = 22, 5 / \ 4 8 / / \ 11
	 * 13 4 / \ / \ 7 2 5 1 return [ [5,4,11,2], [5,8,4,5] ]
	 */

	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}
	
	public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
		ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
		ArrayList<Integer> tmp = new ArrayList<Integer>();
		int median = 0;
		iterator(root, sum, result);
		return result;
	}

	public void recur(TreeNode root, int sum, int median,
			ArrayList<ArrayList<Integer>> result, ArrayList<Integer> tmp) {
		if (root == null)
			return;

		if ((root.left == null) && (root.right == null)
				&& median + root.val == sum) {
			tmp.add(root.val);
			result.add(tmp);
			return;
		}

		else {
			tmp.add(root.val);
			if (root.left != null)
				recur(root.left, sum, median + root.val, result, tmp);
			if (root.right != null)
				recur(root.right, sum, median + root.val, result, tmp);
		}

	}

	public void iterator(TreeNode root, int sum,
			ArrayList<ArrayList<Integer>> result) {
		if (root == null)
			return;
		Stack<TreeNode> stack = new Stack<TreeNode>();
		int tmpCount = 0;
		ArrayList<Integer> tmpList = new ArrayList<Integer>();

		while (root != null || !stack.empty()) {
			while (root != null) {
				stack.push(root);
				root = root.left;
			}

			if (!stack.empty()) {
				root = stack.pop();
				if (root.left == null && root.right == null) {
					for (TreeNode t : stack) {
						tmpList.add(t.val);
						tmpCount += t.val;
					}
					// if this path is the sum path
					if (tmpCount == sum)
						result.add(tmpList);
					
					tmpList = new ArrayList<Integer>();
					tmpCount = 0;
				}
				root = root.right;
			}

		}

	}

	public static void main(String args[]) {
		PathSumTwo pst = new PathSumTwo();
		TreeNode tn = pst.new TreeNode(1);
		ArrayList<ArrayList<Integer>> list = pst.pathSum(tn, 1);
		System.out.println(list.get(0).get(0));
	}

}
